// 82. [递推dfs递归]猴子爬山 https://oj.rnd.huawei.com/problems/82/details
// 顽猴子想去从山脚爬到山顶，途中经过一个有个N个台阶的阶梯，但是这猴子有一个习惯：
// 每一次只能跳1步或跳3步，试问猴子通过这个阶梯有多少种不同的跳跃方式？
// 输入只有一个整数N（0<N<=50）此阶梯有多少个阶梯
// 输出有多少种跳跃方式（解决方案数）
// 输入 3
// 50
// 输出 2
// 122106097
#include <bits/stdc++.h>
using namespace std;

int dfsJump(int n) {
  if (n == 1) {
    return 1;
  }
  if (n == 2) {
    return 1;
  }
  if (n == 3) {
    return 2;
  }
  return dfsJump(n - 1) + dfsJump(n - 3);
}

int jump(int n) {
  int f[100] = {0};
  f[1] = 1;
  f[2] = 1;
  f[3] = 2;
  for (int i = 4; i <= n; i++) {
    f[i] = f[i - 1] + f[i - 3];
  }
  return f[n];
}

int dfsApple(int n) {
  if (n == 1) {
    return 1;
  }
  if (n == 2) {
    return 2;
  }
  return dfsApple(n - 1) + dfsApple(n - 2);
}
int apple(int n) {
  int f[100] = {0};
  f[1] = 1;
  f[2] = 2;
  for (int i = 3; i <= n; i++) {
    f[i] = f[i - 1] + f[i - 2];
  }
  return f[n];
}

int main() {
  //    printf("%d\n", dfsJump(50));
  //    printf("%d\n", jump(50));
  printf("%d\n", dfsApple(40));
  printf("%d\n", apple(40));
  return 0;
}
